package one;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Day_4Sum {
    public List<List<Integer>> fourSum(int[] nums, int target) {

        Arrays.sort(nums);
        List<List<Integer>> list;
        list = new ArrayList<List<Integer>>();
        int mid, right;
        for (int i = 0; i < nums.length - 3; i++) {
            int target_i = target - nums[i];
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int left = i + 1; left < nums.length - 2; left++) {
                mid = left + 1;
                right = nums.length - 1;
                int tmp = target_i - nums[left];
                if (left > i + 1 && nums[left] == nums[left - 1]) {
                    continue;
                }
                while (mid < right) {
                    if (nums[mid] + nums[right] == tmp) {
                        int tmp_mid = nums[mid], tmp_right = nums[right];
                        list.add(Arrays.asList(nums[i], nums[left], nums[mid], nums[right]));
                        while (mid < right && nums[++mid] == tmp_mid) {

                        }
                        while (mid < right && nums[--right] == tmp_right) {
                        }
                    } else if (nums[mid] + nums[right] < tmp) {
                        mid++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Day_4Sum day_4Sum = new Day_4Sum();
        int[] sum = new int[] {-1, -2, -3, 4, 5, 6, 6, 7, 21, 12, 31, 41}; List<List<Integer>> lists = day_4Sum.fourSum(sum, 0);
        System.out.println(lists);
    }
}
